package leetcodev1.链表;

import java.util.HashMap;
import java.util.Map;

public class LeetCode138 {
    //避免无限递归
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();//老节点-新节点

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        if (cachedNode.containsKey(head)) {
            return cachedNode.get(head);
        }

        Node newNode = new Node(head.val);
        cachedNode.put(head, newNode);
        newNode.next = copyRandomList(head.next);
        newNode.random = copyRandomList(head.random);
        return newNode;
    }
}
